package 力扣竞赛.第195场周赛20200628;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/25 19:19
 */
public class No1499_满足不等式的最大值 {
    public static void main(String[] args) {
        Solution1499 solution1499 = new Solution1499();
        //int[][] points = new int[][]{{1, 3}, {2, 0}, {5, 10}, {6, -10}};
        int[][] points = new int[][]{
                {-20,9},
                {-14,10},
                {-11,-7},
                {-6,-2},
                {-2,1},
                {1,-12},
                {3,11},
                {5,13},
                {6,-15},
                {8,18},
                {16,-20},
                {18,-2},
                {20,-11}};
        int maxValueOfEquation = solution1499.findMaxValueOfEquation(points, 8);
        System.out.println(maxValueOfEquation);
    }
}

class Solution1499 {

    public int findMaxValueOfEquation(int[][] points, int k) {
        //要求找出yi+yj+|xi-xj|的最大值,其中|xi-xj|<=k
        //由于:1<=i<j<=points.length
        //所以原式化简:yi+yj+xj-xi = xj+yj+yi-xi
        //于是,固定j,找出 yi-xi的最大值即可
        //具体逻辑:当前元素扔队列,后面的元素加入保证队列单调减少即可!
        //然后移动窗口,当前元素跟头元素比较,相同则干掉!因为前面加过了所以一定可行
        //代码如下:
        //双端队列
        Deque<Integer> deque = new LinkedList<>();
        //队列初始化
        int red = 0;
        int green = 0;
        int max = Integer.MIN_VALUE;
        //以green为基准
        while (green < points.length) {
            if (red == green) {
                green++;
            } else {
                int data = points[green - 1][1] - points[green - 1][0];//加入队列
                if (points[green][0] - points[red][0] <= k) {
                    dealDeque(deque, data);
                    max = Math.max(max, points[green][0] + points[green][1] + deque.getFirst());
                    green++;
                } else {//移动red指针,同时操作双端队列数据增删
                    //当前red指针位置与队列最大元素相同,才删除
                    if (deque.size() != 0 && deque.getFirst() == points[red][1] - points[red][0]) {
                        deque.removeFirst();
                    }
                    red++;
                }
            }
        }
        return max;
    }

    //干掉队列小于data元素并加入data
    public void dealDeque(Deque<Integer> deque, int data) {
        while (deque.size() != 0 && deque.getLast() <= data) {
            deque.removeLast();
        }
        deque.add(data);
    }
}